package leetcode.editor.vip.solution1135;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Soluction1135 {
    public static void main(String[] args) {

    }

    /*int minimumCost(int n, int[][] connections) {
        UF uf = new UF(n + 1);
        // 按照权重进行排序
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        // 记录最小生成树的权重之和
        int mst = 0;
        for (int[] edge : connections) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];

            // 若这条边会产生环，则不能加入 mst
            if (uf.connected(from, to)) continue;

            // 若这条边不会产生环，则属于最小生成树
            mst += weight;

            // 进行连通
            uf.union(from, to);
        }

        // 保证所有节点都被连通
        // 按理说 uf.count() == 1 说明所有节点被连通
        // 但因为节点 0 没有被使用，所以 0 会额外占用一个连通分量
        return mst == 2 ? -1 : mst;
    }

    class UF {
        private int count;
        private int[] parent;

        public UF(int n) {
            parent = new int[n + 1];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int count() {
            return count;
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }

            return parent[x];
        }

        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;

            parent[rootP] = rootQ;
            count--;
        }

    }*/

    public int minCostConnectPoints(int[][] points) {
        List<int[]>[] graph = buildGraph(points.length, points);

        Prim prim = new Prim(graph);
        if (prim.allConnected()) {
            return prim.weightSum();
        }

        return -1;
    }

    public List<int[]>[] buildGraph(int n, int[][] points) {
        LinkedList<int[]>[] graph = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new LinkedList<>();
        }

        for (int[] point : points) {
            // 题目给的节点编号是从 1 开始的，
            // 但我们实现的 Prim 算法需要从 0 开始编号
            int from = point[0] - 1, to = point[1] - 1, weight = point[2];
            graph[from].add(new int[]{from, to, weight});
            graph[to].add(new int[]{to, from, weight});
        }

        return graph;
    }

    // Prim算法实现
    class Prim {
        // 核心数据结构，存储「横切边」的优先级队列
        private PriorityQueue<int[]> pq;
        // 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
        private boolean[] inMST;
        // 记录最小生成树的权重和
        private int weightSum;
        // graph 是用邻接表表示的一幅图，
        // graph[s] 记录节点 s 所有相邻的边，
        // 三元组 int[]{from, to, weight} 表示一条边
        private List<int[]>[] graph;

        public Prim(List<int[]>[] graph) {
            this.graph = graph;
            // 按照权重从小到大排序
            pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
            int n = graph.length;
            inMST = new boolean[n];

            // 随机选择一个节点
            cut(0);
            inMST[0] = true;

            while (!pq.isEmpty()) {
                int[] poll = pq.poll();
                int to = poll[1], weight = poll[2];

                if (inMST[to]) {
                    // 节点 to 已经在最小生成树中，跳过
                    // 否则这条边会产生环
                    continue;
                }

                weightSum += weight;
                inMST[to] = true;
                cut(to);
            }
        }

        // 将 s 的横切边加入优先队列
        private void cut(int s) {
            // 遍历 s 的邻边
            for (int[] edge : graph[s]) {
                int to = edge[1];
                // 存在重复的，不再加入
                if (inMST[to]) {
                    continue;
                }

                // 加入横切边队列
                pq.offer(edge);
            }
        }

        // 最小生成树的权重和
        public int weightSum() {
            return weightSum;
        }

        // 判断最小生成树是否包含图中的所有节点
        public boolean allConnected() {
            for (int i = 0; i < inMST.length; i++) {
                if (!inMST[i]) {
                    return false;
                }
            }
            return true;
        }
    }
}
